package com.azure.code.dfs.island;

import java.util.HashSet;

/**
 * 不同岛屿的数量
 * Number of Distinct Islands
 * 0代表海水，1表示陆地，计算不同的岛屿数量
 * 关键：把岛屿转化成字符串 --》 序列化
 */
public class Island_694 {

    int numDistinctIslands(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // 记录所有岛屿的序列化结果
        HashSet<String> islands = new HashSet<>();
        for(int i = 0; i < m; i++){
            for (int j = 0; j < n; j++) {
                if(grid[i][j]==1){
                    StringBuilder sb = new StringBuilder();
                    // 初始方向可以随便写，不影响正确性
                    dfs(grid,i,j,sb,666);
                    islands.add(sb.toString());
                }
            }
        }
        islands.forEach(System.out::println);
        // 不同的岛屿数量
        return islands.size();
    }

    private void dfs(int[][] grid,int i,int j, StringBuilder sb,int dir) {
        int m = grid.length,n=grid[0].length;
        if(i <0 || j<0 || i>=m || j>=n || grid[i][j] == 0) return;
        grid[i][j] = 0;
        sb.append(dir).append(",");
        dfs(grid,i-1,j,sb,1);
        dfs(grid,i+1,j,sb,2);
        dfs(grid,i,j-1,sb,3);
        dfs(grid,i,j+1,sb,4);
        sb.append(-dir).append(",");
    }
    public static void main(String[] args) {
        int[][] grid = {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
        System.out.println(new Island_694().numDistinctIslands(grid));
        int[][] grid2 = {{1,1,0,1,1},{1,0,0,0,0},{0,0,0,0,1},{1,1,0,1,1}};
        System.out.println(new Island_694().numDistinctIslands(grid2));
    }
}
